# -*- coding: utf-8 -*-

"""115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：
1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成"""

class Solution:
    """
    建立 t*s 矩阵，(i,j) = t[i] == s[j]。那么这道题就变成求总首行某个点开始，往右下方到达尾行经过 1 的路径，且长度为 t 的路径数目。
    这道题可以不用递归先给计算过程，直接用递推的动态规划更直观。如上面的示例2，首先建立的字符相等矩阵 M：
                (s[j])
               b a b g b a g
            b  1 0 1 0 1 0 0
    (t[i])  a  0 1 0 0 0 1 0
            g  0 0 0 1 0 0 1

    定义 dp[i][j] 为在 s 的编号前 j 个字符中，包含的t的编号前 i 的字符前缀的个数。
    画成图就是以矩阵中的 1 为顶点，从首行到尾行一行一步沿右下方向连接两个顶点的有向图。最后找距离为 lt 的路径数目。
    先在草稿纸上作图，一下递推规律就跃然纸上。
    递归定义：
        dp[i][j] = dp[i][j-1] + dp[i-1][j-1]      # M[i][j] = 1
        dp[i][j] = dp[i][j-1]                     # M[i][j] = 0
    地推基础：
        dp[0][0] = M[0][0]
        dp[i][0] = 0                              # i > 0
        dp[0][j] = dp[0][j-1] + 1                 # if M[0][j] == 1
        dp[0][j] = dp[0][j-1]                     # if M[0][j] == 0
    上述矩阵 M 的递推结果如下：
                (s[j])
               b a b g b a g
            b  1 1 2 2 3 3 3
    (t[i])  a  0 1 1 1 1 4 4
            g  0 0 0 1 1 1 5
    """
    def numDistinct(self, s: str, t: str) -> int:
        lt, ls = len(t), len(s)
        M = [[0 for _ in range(ls)] for _ in range(lt)]

        i = 0
        while i < lt:
            j = 0
            while j < ls:
                M[i][j] = 1 if t[i] == s[j] else 0
                j += 1
            i += 1

        # for foo in M:
        #     print(foo)
        # print('-----------------------------')

        dp = [[0 for _ in range(ls)] for _ in range(lt)]

        dp[0][0] = M[0][0]
        i = 1
        while i < lt:
            dp[i][0] = 0
            i += 1
        j = 1
        while j < ls:
            dp[0][j] = (dp[0][j-1] + 1) if M[0][j] == 1 else dp[0][j-1]
            j += 1

        i = 1
        while i < lt:
            j = 1
            while j < ls:
                if M[i][j] == 1:
                    dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
                j += 1
            i += 1

        # for foo in dp:
        #     print(foo)

        return dp[-1][-1]

if __name__ == '__main__':
    rs = Solution().numDistinct(s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", t = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
    # rs = Solution().numDistinct(s = "babgbag", t = "bag")
    print(rs)
